﻿#define  _CRT_SECURE_NO_WARNINGS
//给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
//
//回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
//
//例如，121 是回文，而 123 不是。
//
//
//示例 1：
//
//输入：x = 121
//输出：true
//示例 2：
//
//输入：x = -121
//输出：false
//解释：从左向右读, 为 - 121 。 从右向左读, 为 121 - 。因此它不是一个回文数。
//示例 3：
//
//输入：x = 10
//输出：false
//解释：从右向左读, 为 01 。因此它不是一个回文数。
//
//来源：力扣（LeetCode）
//链接：https ://leetcode.cn/problems/palindrome-number
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
//简单版本：
bool isPalindrome(int x) {
    if (x < 0)
        return false;
    else {
        long y = x;
        long sum = 0;
        while (x) {
            int c = x % 10;
            sum *= 10;
            sum += c;
            x /= 10;
        }
        if (sum == y)
            return true;
    }
    return false;
}
//进阶版本：
bool isPalindrome(int x) {
    if (x < 0)
        return false;
    int div = 1;
    while (x / div >= 10)
        div *= 10;
    while (x) {
        int left = x % 10;
        int right = x / div;
        if (left != right)
            return false;
        x = (x % div) / 10;//去头又去尾
        div /= 100;//在前面的操作中x的指数级降了10^2,所以div也要减小10^2

    }
    return true;
}
//给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n / 2 ⌋ 的元素。
//
//你可以假设数组是非空的，并且给定的数组总是存在多数元素。
//
//来源：力扣（LeetCode）
//链接：https ://leetcode.cn/problems/majority-element
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

//摩尔投票法：
int majorityElement(int* nums, int numsSize) {//摩尔投票法
    int flag = nums[0];//假设flag便是多数元素
    int b = 1;//假设flag就是多数元素
    int j = 0;
    for (j = 1;j < numsSize;j++) {
        if (flag == nums[j])
        {
            b++;
        }
        else {
            b--;//不是就换
        }
        if (b == 0) {//如果flag真的是多数元素的话b就会大于或等于1
            flag = nums[j];//假设
            b = 1;
        }
    }
    return flag;

}
//快排：
int cmp(const void* p1, const void* p2) {
    return *((int*)p1) - *((int*)p2);
}
int majorityElement(int* nums, int numsSize) {
    qsort(nums, numsSize, sizeof(nums[0]), cmp);
    return nums[(numsSize - 1) / 2];

}